The present invention relates to digital data processing, and more particularly to interpolation of video and audio digital data. Video data may represent a still image or a moving picture.
Data interpolation is widely technique in digital data processing. One example is data compression employing a fast wavelet transform. See W. Sweldens, P. Schröder, “Building your own wavelets at Home”, in Wavelets in Computer Graphics, pages 15-87, ACM SIGGRPH Course notes, 1996, available on Wide World Web at http://cm.bell-labs.com/who/wim/papers/papers.html#athome, incorporated herein by reference. A fast wavelet transform based on a lifting scheme uses prediction. Some data values are replaced with the differences between the data value and some predicted value. Let a set of samples S0, S1, . . . SN−1 represent an original signal S. This set can be a sequence of digital image data values (video data values) at consecutive image points (pixels). These values may be the values of some component of RGB, YCbCr, or some other color representation. This set is subdivided into two subsets. On subset is the set of even samples S0, S2, S4 . . . , and the other subset is the set of odd samples S1, S3, S5 . . . The even samples are modified with a weighted sum of the odd samples to form a set of low-pass coefficients representing a downsampled low-resolution version of the original set. For the odd indices of the form 2n+1 (n=0, 1, . . . ), the wavelet transform replaces the odd sample values S2n+1 with the differencesY2n+1=S2n+1−P2n+1  (1)where the predicted value P2n+1 is a function of the even sample values. P2n+1 can be calculated by interpolation.
The high pass coefficients Y2n+1 form a downsampled residual version of the original data set. The original data set can be perfectly reconstructed from the low pass coefficients and the high pass coefficients.
The low pass coefficients can be processed with another iteration of the fast wavelet transform.
If the prediction P is good, then the set of the high pass coefficients will have many zeroes and small values. Consequently, separate compression of the high pass coefficients will yield a high compression ratio when compression techniques such as quantization, Huffman coding, Zero Tree coding, or others are employed.
Good prediction can be obtained for a well correlated signal S if the predictor P2n+1 is a value of a polynomial that coincides with the signal S at even points near 2n+1. For example, P2n+1 can be the value at point 2n+1 of a cubic polynomial which coincides with S at points 2n−2, 2n, 2n+2, 2n+4. We will denote this “cubic predictor” as P(1). It can be shown that if consecutive pixels 0, 1, 2 . . . are equidistant from each other then:P(1)2n+1=(−S2n−2+9S2n+9S2n+2−S2n+4)/16  (2)
JPEG standard 2000, as described in “JPEG 2000 Final Committee Draft version 1.0”, dated 16 Mar. 2000, recommends using the cubic predictor for lossy compression. For lossless compression, JPEG standard 2000 recommends a linear predictor given by the following equation:P2n+1=P(2)2n+1=(S2n+S2n+2)/2  (3)
With the lossy compression the following problems have been observed. If the prediction uses the linear predictor P(2), the edges (the regions of an abrupt change of S) become smeared. If the cubic predictor P(1) is used, the image areas near the edges contain artifacts. Higher order polynomial predictors result in more artifacts.
In some wavelet transform implementations, the predictor value depends on whether or not an edge is detected. We will call such predictors “edge dependent”. In one implementation, if no edge is detected near a point 2n+1, the predictor value P2n+1 is calculated as the cubic value P(1)2n+1 or the value of some higher order polynomial predictor. If an edge is detected, the predictor value P2n+1 is the linear value P(2). The results achieved with this method depend on the edge detection technique. According to one article, an edge can be detected by determining if the data S is “well approximated by a low order polynomial.” See R. L. Claypoole, Jr. et al., “Nonlinear Wavelet Transforms for Image Coding via Lifting”, Submitted to IEEE Transactions on Image Processing (EDICS #'s: 1-STIL and 2-WAVP, Aug. 25, 1999).
It is desirable to find good edge detection techniques that provide good prediction for many images (and hence good image reconstruction with lossy compression) and are simple to implement with a computer or other digital circuitry. It is also desirable to find good predictors (simple to implement and providing good prediction) for use with both edge dependent and edge independent wavelet transforms. Further, interpolation based on edge detection and prediction can be employed for compression of any digital signal correlated in space or time. Possible applications include photography, moving pictures, ultra sound imaging (tomography), poly-dimension object modeling, and others. Digital zoom can be implemented with a reverse wavelet transform by setting the high pass coefficients to zero. Good interpolation techniques are desirable.